package com.longge;

/**
 * @创建人 xinglongge
 * @创建时间 2021/9/22
 * @描述
 */
public class MinDifficulty {

    public int minDifficulty(int[] jobDifficulty, int d) {
        if (jobDifficulty.length <= 0 || d <= 0 || jobDifficulty.length < d) {
            return -1;
        }
        int n = jobDifficulty.length;
        //dp[i][j] 表示第i天，完成第j个任务，需要的最小工作量 其中i<=j
        int[][] dp = new int[d][n];
        //第一天完成0到n-1项工作，难度等于0到n-1中最大的难度
        int max = 0;
        for (int j = 0; j < n; j++) {
            max = Math.max(max, jobDifficulty[j]); //当天完成j项任务最大难度
            dp[0][j] = max;
        }
        // 第二天开始
        for (int i = 1; i < d; i++) {
            //从第i项工作开始（每天至少完成一项，第i天至少已经完成前i-1项）
            for (int j = i; j < n; j++) {
                //开始遍历求 初始化max，minSum
                max = 0;
                int minSum = Integer.MAX_VALUE;
                //当天工作量=前k-1项+当天最大难度 ；
                for (int k = j; k >= i; k--) {
                    max = Math.max(max, jobDifficulty[k]);
                    minSum = Math.min(minSum, max + dp[i - 1][k - 1]);
                }
                dp[i][j] = minSum;
            }
        }
        return dp[d - 1][n - 1];
    }

}
